home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c / pro12 / msort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-31  |  3.9 KB  |  142 lines
  1. /***********************************************************************/
  2. /*  SORT(): Non-Recursive Merge Sort function.                         */
  3. /*  See the function declaration for calling information.              */
  4. /* Function is by Bruce Feist; please contact me on CompuServe with    */
  5. /*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
  6. /*    questions or problems.                                           */
  7. /* You can also reach me at the Enlightened Board, at (703) 370-9528,  */
  8. /*   N/8/1                                                             */
  9. /* Feel free to make use of this code in your own programs.            */
  10. /***********************************************************************/
  11.  
  12. /* Merge sort.  Fast, but uses lots of space. */
  13.  
  14. #include <alloc.h>
  15. #include <mem.h>
  16. #include <stddef.h>
  17. #include <stdio.h>
  18.  
  19. #include "sort.h"
  20.  
  21. #define VERBOSE (0)
  22.  
  23. static char *base, *last_ptr, *temp_base;
  24. static unsigned int nelem, width;
  25. static int (*compare) (void *, void *);
  26. static void merge (char *, unsigned int);
  27. #if VERBOSE
  28. static void show_array (void *, int);
  29. #endif
  30.  
  31. int
  32. msort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
  33. {
  34.   long sublist_length, sublist_offset;
  35.   unsigned int list_size;
  36.  
  37.   base = pbase;
  38.   nelem = pnelem;
  39.   width = pwidth;
  40.   compare = pcompare;
  41.  
  42. #if VERBOSE
  43.   printf ("Msort (%p, %d, %d, %p).\n", pbase, pnelem, pwidth, pcompare);
  44. #endif
  45.  
  46.   list_size = nelem * width;
  47.  
  48.   temp_base = malloc (list_size);
  49.   if (temp_base == NULL)
  50.     return S_NOMEM;
  51.  
  52.   last_ptr = base + list_size - width;
  53.  
  54.   /* We first merge sublists of length 1, then of length 2, and */
  55.   /* so on, doubling each time.                                 */
  56.  
  57.   for (sublist_length = width;
  58.        sublist_length < list_size;
  59.        sublist_length <<= 1)
  60.   {
  61.     for (sublist_offset = 0;
  62.          sublist_offset + sublist_length < list_size;
  63.          sublist_offset +=  sublist_length << 1)
  64. #pragma warn -sig
  65.        merge (base + sublist_offset, (unsigned int) sublist_length);
  66. #pragma warn .sig
  67.      } /* for sublist_length */
  68.  
  69.   free (temp_base);
  70.  
  71.   return S_OK;
  72.   }  /* end msort */
  73.  
  74.  
  75. void
  76. merge (char *left_base, unsigned int length)
  77. {
  78.   char *left_ptr, *right_ptr, *left_max, *right_max, *result_ptr;
  79.  
  80. #if VERBOSE
  81.   printf ("Merge (%p, %u)\n", left_base, length);
  82. #endif
  83.  
  84.   left_ptr = left_base;
  85.   right_ptr = left_base + length;
  86.   left_max = right_ptr - width;
  87.   right_max = (length > last_ptr - right_ptr) ? last_ptr : left_max + length;
  88.  
  89. #if VERBOSE
  90.   fputs ("Input: ", stdout);
  91.   show_array (left_base, (right_max - left_base + width) / sizeof (double));
  92.  
  93.   if (length > 20000)
  94.     printf ("Merging %p - %p with %p - %p.\n",
  95.           left_ptr, left_max, right_ptr, right_max);
  96. #endif
  97.  
  98.  
  99.   result_ptr = temp_base;
  100.   while (1)
  101.   {
  102.     if (compare (left_ptr, right_ptr) > 0)
  103.     {
  104.       memcpy (result_ptr, right_ptr, width);
  105.       right_ptr += width;
  106.       result_ptr += width;
  107.       if (right_ptr > right_max)
  108.       {
  109.         memcpy (result_ptr, left_ptr, left_max - left_ptr + width);
  110.         break;
  111.         }
  112.       }
  113.     else
  114.     {
  115.       memcpy (result_ptr, left_ptr, width);
  116.       left_ptr += width;
  117.       result_ptr += width;
  118.       if (left_ptr > left_max)
  119.       {
  120.         memcpy (result_ptr, right_ptr, right_max - right_ptr + width);
  121.         break;
  122.         }
  123.       }
  124.     }  /* end while */
  125.  
  126.  
  127. #if VERBOSE
  128.   printf ("Copying %d bytes from %p to %p.\n",
  129.           right_max - left_base + width, temp_base, left_base);
  130.   fputs ("Intermediate: ", stdout);
  131.   show_array (temp_base, (right_max - left_base + width) / sizeof (double));
  132. #endif
  133.  
  134.   memcpy (left_base, temp_base, right_max - left_base + width);
  135.  
  136. #if VERBOSE
  137.   fputs ("Output: ", stdout);
  138.   show_array (left_base, (right_max - left_base + width) / sizeof (double));
  139. #endif
  140.  
  141.   } /* end merge */
  142.